Friday, November 11, 2005

The F.L.A.M.E.S. problem -- SOLVED!!

UPDATE: Here is a first draft



:) I (and a friend of mine P) have come up with a rigorous solution to the FLAMES problem! It turns out to have a really simple (though not quite obvious) and extremely elegant solution. Full writeup of the proof to be posted within the next few hours.

7 Comments:

At 1:39 AM, Blogger Artful Badger said...

Try to push it through the 'Journal of Teen Romance' ;). Actually, I am curious to see your proof.

 
At 2:39 PM, Blogger A linearizer said...

:) Actually I'm seriously thinking of submitting this to a real CS conference. When the problem is simplified and generalized to dynamics over any finite string (not just FLAMES), the properties of this game seem to have some completely cool and unexpected (though not particularly deep) connections to number theory and symbolic dynamics. But I'm getting ahead of myself here -- I need to first make sure that the bird is in hand rather than in the bushes.

 
At 9:45 PM, Blogger Artful Badger said...

You are essentially stating that the remainder left at the end of each stage must be the same if 2 values of the difference generate the same string s'. But, what if you are only interested in the final answer? (something)M. That would lead to a lot more flexibility - 2 values of m will map to the same value a lot more frequently. The first stage cannot have m mod 6 = 4. The second cannot have m mod 5 = 3 in 3 of the cases and m mod 5 = 4 in 2 of the cases (depending on which character is removed). That is essentially why it becomes very complicated to work back. You could have a computer develop a tree for this and have a set of "rules" for selecting m. On an average, 1 in 6 values of m should give your answer so it shouldn't be too hard to find m.

 
At 9:26 AM, Blogger Primalsoup said...

OHT! :) I am glad that I have started something that will make it to the Journal of Teen Romance. But please tell me there is no such thing, else I will conclude that I have had a very deprived life! :)

Anyway, even if the game is fair mathematically... reality is otherwise. *Sigh* And that is the big tragedy...

 
At 10:51 AM, Blogger A linearizer said...

[Ramani] - Yes, you have gotten the general idea but what I didnt spell it out fully was the permutation case is needed to exactly solve for the final outcome situation.

"On an average, 1 in 6 values of m should give your answer so it shouldn't be too hard to find m.". It turns out that each of the letters of FLAMES appear with equal likelihood in the LCM(1,2,..6) = 60 possible sequences in the FLAMES case. However without explicitly proving why this MUST be so, there is no a priori reason to believe that this would hold true for strings of any arbitrary length. That is the next step now that we have shown that everything interesting occurs when m is in the range 1 to LCM(1,...|s|)

 
At 11:08 AM, Blogger A linearizer said...

[PrimordialSoup] - If there isnt a Journal of Teen/Closet Romance, maybe its time to get one started.

As for reality being tragically otherwise, this analysis should bring some optimism as it suggests that inevitably there is always some kind of formula/technique to proactively manipulate "destiny" to (eventually) get what you want. This assumes you know what it is that you want -- which is a challenge that nobody really knows quite how to solve and few ever solve in their entire lifetimes, do they?

 
At 12:19 PM, Blogger A linearizer said...

:) Its in Kenya too!! S = "Sweethearts" makes far more sense than "Support" (whatever that means).

 

Post a Comment

<< Home